package datastructures;

import java.util.*;

/**
 * A simple binary searchtree ordered by the method compareTo for the elements.
 * 
 * @author (Bror Bjerner)
 * @version (2007)
 */

public class BinarySearchTree<E extends Comparable<? super E>> extends
		AbstractCollection<E> {

	protected Entry root;
	protected int size;

	protected class Entry {

		public E element;
		public Entry left, right, parent;

		public Entry(E element, Entry left, Entry right, Entry parent) {

			this.element = element;
			this.left = left;
			this.right = right;
			this.parent = parent;

		} // constructor Entry

		public Entry(E element, Entry parent) {
			this(element, null, null, parent);
		} // constructor Entry

	} // class Entry

	/**
	 * The constructor creates the empty tree.
	 */
	public BinarySearchTree() {
		super();
		root = null;
		size = 0;
	} // constructor BinarySearchTree

	/**
	 * The number of objects in this collection.
	 * 
	 * @return the number of elements in the tree.
	 */
	public int size() {
		return size;
	} // size

	/**
	 * Create an iterator for elements in the tree in inorder.
	 * 
	 * @return the created iterator.
	 */
	public Iterator<E> iterator() {
		return new BST_Iterator();
	} // iterator

	protected void addIn(E newElem, Entry t) {
		if (newElem.compareTo(t.element) < 0)
			if (t.left == null)
				t.left = new Entry(newElem, t);
			else
				addIn(newElem, t.left);
		else if (t.right == null)
			t.right = new Entry(newElem, t);
		else
			addIn(newElem, t.right);
	} // addIn

	/**
	 * Add the element into the three at first proper empty place
	 * 
	 * @param o
	 *            the element to be included
	 * @returns true if the element is in included in the tree.
	 */
	public boolean add(E elem) {
		if (root == null)
			root = new Entry(elem, null);
		else
			addIn(elem, root);
		size++;
		return true;
	} // add

	protected Entry find(E elem, Entry t) {

		if (t == null)
			return null;
		else {
			int jfr = elem.compareTo(t.element);
			if (jfr < 0)
				return find(elem, t.left);
			else if (jfr > 0)
				return find(elem, t.right);
			else
				return t;
		}
	} // find

	/**
	 * Check if the element is in the the tree.
	 * 
	 * @param elem
	 *            The element to check
	 * @returns true if the element is contained in the tree, otherwise false is
	 *          returned.
	 */
	public boolean contains(E elem) {
		return find(elem, root) != null;
	} // contains

	/**
	 * Removes all of the elements from this tree
	 */
	public void clear() {
		root = null;
		size = 0;
	} // clear

	protected Entry findRefToMostRight(Entry t) {
		if (t.right == null)
			return t;
		else
			return findRefToMostRight(t.right);
	} // findRefToMostRight

	protected void removeLeaf(Entry leaf, Entry parent) {
		if (parent == null)
			root = null;
		else if (parent.left == leaf)
			parent.left = null;
		else
			parent.right = null;
	} // removeLeaf

	protected void removeThis(Entry t) {
		if (t.left == null)
			if (t.right == null)
				removeLeaf(t, t.parent);
			else {
				t.element = t.right.element;
				t.left = t.right.left;
				if (t.left != null)
					t.left.parent = t;
				t.right = t.right.right;
				if (t.right != null)
					t.right.parent = t;
			}
		else {
			Entry bytEntry = findRefToMostRight(t.left);
			t.element = bytEntry.element;
			if (bytEntry == t.left) {
				t.left = bytEntry.left;
				if (t.left != null)
					t.left.parent = t;
			} else {
				bytEntry.parent.right = bytEntry.left;
				if (bytEntry.left != null)
					bytEntry.left.parent = bytEntry.parent;
			}
		}
		size--;
	} // removeThis

	/**
	 * Remove the first occurance of an element for which compareTo with the
	 * argument yields 0. If no element is removed false is returned, otherwise
	 * true.
	 * 
	 * @param elem
	 *            element of Comarable
	 * @return true if the tree has changed, otherwise false.
	 */
	public boolean remove(E elem) {
		Entry remElem = find(elem, root);
		if (remElem == null)
			return false;
		else {
			removeThis(remElem);
			return true;
		}
	} // remove

	// An inner class to create an iterator for
	// the collection of elements.
	protected class BST_Iterator implements Iterator<E> {
		private Stacks<Entry> nextOnTop = new LinkedStack<Entry>();
		private Entry lastNext = null;
		private boolean remAllowed = false;

		protected BST_Iterator() {
			for (Entry p = root; p != null; p = p.left)
				nextOnTop.push(p);
		} // constructor BST_Iterator

		public boolean hasNext() {
			return !nextOnTop.isEmpty();
		} // hasNext

		public E next() {
			lastNext = nextOnTop.pop();
			// throws NoSuchElementException if empty
			for (Entry p = lastNext.right; p != null; p = p.left)
				nextOnTop.push(p);
			remAllowed = true;
			return lastNext.element;
		} // next

		public void remove() {
			if (remAllowed) {
				removeThis(lastNext);
				remAllowed = false;
			} else
				throw new IllegalStateException();
		} // remove
	} // classBST_Iterator
} // class BinarySearchTree
